! git log -1 --format="%H"
497b097917797016a5c8d397282faf8cdc866d11
import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product
import gurobipy as gp
from gurobipy import GRB, quicksum
# These are ours
import problem
import visualization
Looking in indexes: https://pypi.gurobi.com Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1) Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3) Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0) Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3) Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0) Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)
def normalize(i, j):
assert i != j
return (i, j) if i < j else (j, i)
from model import Autonomax, Config
# Run on the first |C| cities (mostly for testing)
C = 41
# What scenario we will be utilizing
scenario = 0
# The number of cities in the core net
NC = 4
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 1
autonomax = Autonomax(
Config(
cities=problem.cities[:C],
distances=problem.D[:C, :C],
demand=problem.B[scenario][:C],
core_city_count=NC,
core_net_is_cycle=Z,
)
)
Academic license - for non-commercial use only - expires 2021-05-15 Using license file /Users/sjurwold/gurobi.lic
idx = next(v for v,city in enumerate(problem.cities) if city=="Östersund")
ostersund_cc = autonomax.model.addConstr(
(autonomax.is_control_center[idx] == 1)
)
A = autonomax.model.getA()
count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1
V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())
print(f'V = {V}, C = {C}')
fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)
total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
constraints_in_set = count(constraint)
print(f'{constraints_in_set:>5} | {name}')
#plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
total += constraints_in_set
plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
variables_in_set = count(variables)
print(f'{variables_in_set:>5} | {name}')
#plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
total += count(variables)
plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
plt.savefig('constraint-matrix.png', dpi=200)
V = 9389, C = 6153
CONSTRAINT SETS:
1 | one_control_center
41 | control_city_directly_connected
1681 | reduce_control_center_symmetry
41 | core_city_ub
1 | cycle_or_path
41 | disallow_core_tree
1 | exactly_nc_core_cities
41 | control_center_is_connected
2460 | is_connectable
123 | is_connected_timestep
41 | connected_graph
41 | conservation_of_flow
820 | force_edge_if_flow
820 | edge_cost_lb
VARIABLE SETS:
41 | is_control_center
820 | is_core_edge
41 | is_core_city
164 | is_connected_step
5043 | is_connectable_step
820 | flow
820 | abs_flow
820 | is_sub_edge
820 | edge_cost
autonomax.model.Params.timeLimit = 600.0
autonomax.model.optimize()
Changed value of parameter timeLimit to 600.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 6154 rows, 9389 columns and 30300 nonzeros
Model fingerprint: 0xbafe4d90
Model has 4 SOS constraints
Model has 820 general constraints
Variable types: 2460 continuous, 6929 integer (6929 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+05]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+02]
RHS range [7e-01, 4e+01]
Presolve removed 952 rows and 3495 columns
Presolve time: 0.06s
Presolved: 5202 rows, 5894 columns, 24976 nonzeros
Variable types: 2460 continuous, 3434 integer (3434 binary)
Found heuristic solution: objective 92147.268277
Found heuristic solution: objective 76955.725974
Root relaxation: objective 7.412998e+03, 7951 iterations, 0.19 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 7412.99762 0 230 76955.7260 7412.99762 90.4% - 0s
H 0 0 75149.913121 7412.99762 90.1% - 0s
H 0 0 38444.424737 7412.99762 80.7% - 0s
0 0 8645.23655 0 336 38444.4247 8645.23655 77.5% - 0s
0 0 8646.58859 0 309 38444.4247 8646.58859 77.5% - 0s
0 0 8646.58859 0 307 38444.4247 8646.58859 77.5% - 0s
0 0 8907.29676 0 401 38444.4247 8907.29676 76.8% - 0s
0 0 8907.29676 0 393 38444.4247 8907.29676 76.8% - 0s
0 0 8907.29676 0 384 38444.4247 8907.29676 76.8% - 0s
H 0 0 30568.787814 8907.29676 70.9% - 1s
0 0 8907.29676 0 423 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 377 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 366 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 361 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 356 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 368 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 375 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 363 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 374 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 361 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 373 30568.7878 8907.29676 70.9% - 1s
0 0 8907.29676 0 373 30568.7878 8907.29676 70.9% - 1s
H 0 0 23074.151017 8907.29676 61.4% - 1s
0 2 8907.29676 0 351 23074.1510 8907.29676 61.4% - 2s
H 73 70 22807.419343 9016.27513 60.5% 237 3s
H 73 70 22542.574249 9016.27513 60.0% 237 3s
H 74 70 22187.648246 9016.27513 59.4% 234 3s
H 114 105 21808.381228 9016.27513 58.7% 189 3s
H 114 105 21414.537481 9016.27513 57.9% 189 3s
H 115 105 21389.412153 9016.27513 57.8% 187 3s
H 116 105 21389.330867 9016.27513 57.8% 186 3s
H 117 105 21225.493366 9016.27513 57.5% 185 3s
H 118 105 20970.709536 9016.27513 57.0% 183 3s
H 291 259 20822.843234 9016.27513 56.7% 126 3s
H 326 284 20752.299978 9016.27513 56.6% 128 4s
H 327 284 20719.697372 9016.27513 56.5% 128 4s
H 602 496 20689.252922 9016.27513 56.4% 112 4s
H 605 495 20652.547989 9016.27513 56.3% 112 4s
H 609 495 20646.921786 9016.27513 56.3% 112 4s
685 587 13680.5277 136 214 20646.9218 9016.27513 56.3% 112 5s
H 808 686 20643.411690 9016.27513 56.3% 106 5s
H 841 690 20622.967241 9016.27513 56.3% 106 5s
H 844 687 20612.967241 9016.27513 56.3% 106 5s
H 1162 874 20586.484021 9016.27513 56.2% 116 6s
1518 1104 18133.4801 151 350 20586.4840 9016.27513 56.2% 105 10s
H 1521 1050 20585.252764 9016.27513 56.2% 105 11s
1525 1056 9953.48209 12 319 20585.2528 9101.58334 55.8% 130 16s
1562 1077 10358.5144 17 340 20585.2528 9675.72780 53.0% 135 20s
H 1594 1034 20435.252764 10004.4978 51.0% 139 20s
1822 1057 18570.9916 36 132 20435.2528 10309.1646 49.6% 156 25s
2387 1103 16942.6273 28 245 20435.2528 10649.4410 47.9% 176 30s
3013 1029 cutoff 28 20435.2528 13148.6477 35.7% 198 35s
3890 941 infeasible 58 20435.2528 15185.5254 25.7% 200 40s
H 3996 885 20400.910366 15246.2004 25.3% 200 40s
4959 824 19569.4261 30 219 20400.9104 16880.5468 17.3% 205 45s
5857 730 cutoff 39 20400.9104 17881.6248 12.3% 211 50s
7267 590 cutoff 36 20400.9104 19230.7008 5.74% 202 55s
Cutting planes:
Gomory: 36
Cover: 126
Implied bound: 1
MIR: 73
Flow cover: 130
GUB cover: 1
Inf proof: 3
Zero half: 16
RLT: 183
Relax-and-lift: 2
Explored 17209 nodes (1581340 simplex iterations) in 58.52 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 20400.9 20435.3 20585.3 ... 20689.3
Optimal solution found (tolerance 1.00e-04)
Best objective 2.040091036565e+04, best bound 2.040091036565e+04, gap 0.0000%
city_info = pd.DataFrame(autonomax.city_info())
city_info
| Index | Name | IsCoreCity | IsControlCenter | Demand | IngoingFlow | OutgoingFlow | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Boden | False | False | 4.5 | 4.000000e+00 | 8.5 |
| 1 | 1 | Borås | False | False | 0.7 | 1.030000e+01 | 11.0 |
| 2 | 2 | Eskilstuna | False | False | 1.1 | 2.520000e+01 | 26.3 |
| 3 | 3 | Falun | False | False | 2.3 | 0.000000e+00 | 2.3 |
| 4 | 4 | Gävle | False | False | 1.0 | 1.900000e+00 | 2.9 |
| 5 | 5 | Göteborg | False | False | 5.8 | 0.000000e+00 | 5.8 |
| 6 | 6 | Halmstad | False | False | 3.4 | 6.100000e+00 | 9.5 |
| 7 | 7 | Haparanda | False | False | 4.6 | 3.078426e-12 | 4.6 |
| 8 | 8 | Helsingborg | False | False | 2.2 | 3.900000e+00 | 6.1 |
| 9 | 9 | Hudiksvall | False | False | 3.9 | 6.969536e-12 | 3.9 |
| 10 | 10 | Jönköping | False | False | 1.2 | 1.237055e-11 | 1.2 |
| 11 | 11 | Kalmar | False | False | 4.0 | 1.600000e+00 | 5.6 |
| 12 | 12 | Karlskrona | False | False | 1.6 | 0.000000e+00 | 1.6 |
| 13 | 13 | Karlstad | False | False | 0.9 | 0.000000e+00 | 0.9 |
| 14 | 14 | Kiruna | False | False | 4.0 | 0.000000e+00 | 4.0 |
| 15 | 15 | Kristianstad | False | False | 3.0 | 0.000000e+00 | 3.0 |
| 16 | 16 | Lidköping | False | False | 1.2 | 1.340000e+01 | 14.6 |
| 17 | 17 | Linköping | False | False | 4.1 | 7.400000e+00 | 11.5 |
| 18 | 18 | Luleå | False | False | 2.0 | 1.310000e+01 | 15.1 |
| 19 | 19 | Malmö | False | False | 2.6 | 1.300000e+00 | 3.9 |
| 20 | 20 | Motala | False | False | 2.4 | 1.200000e+00 | 3.6 |
| 21 | 21 | Norrköping | False | False | 1.7 | 1.890000e+01 | 20.6 |
| 22 | 22 | Nyköping | False | False | 4.6 | 0.000000e+00 | 4.6 |
| 23 | 23 | Sandviken | True | False | 4.5 | 5.200000e+00 | 9.7 |
| 24 | 24 | Skellefteå | False | False | 4.4 | 1.510000e+01 | 19.5 |
| 25 | 25 | Skövde | False | False | 2.5 | 1.100000e+01 | 13.5 |
| 26 | 26 | Stockholm | False | False | 7.0 | 4.228617e-12 | 7.0 |
| 27 | 27 | Sundsvall | True | False | 0.7 | 1.108000e+02 | 111.5 |
| 28 | 28 | Trelleborg | False | False | 1.3 | 3.907319e-12 | 1.3 |
| 29 | 29 | Uddevalla | False | False | 4.0 | 5.800000e+00 | 9.8 |
| 30 | 30 | Umeå | False | False | 3.2 | 1.950000e+01 | 22.7 |
| 31 | 31 | Uppsala | False | False | 1.9 | 0.000000e+00 | 1.9 |
| 32 | 32 | Varberg | False | False | 0.8 | 9.500000e+00 | 10.3 |
| 33 | 33 | Vetlanda | False | False | 2.1 | 5.300000e+00 | 7.4 |
| 34 | 34 | Vänersborg | False | False | 3.6 | 9.800000e+00 | 13.4 |
| 35 | 35 | Västervik | False | False | 1.8 | 5.600000e+00 | 7.4 |
| 36 | 36 | Västerås | True | False | 1.4 | 7.970000e+01 | 81.1 |
| 37 | 37 | Växjö | False | False | 2.3 | 3.000000e+00 | 5.3 |
| 38 | 38 | Örebro | False | False | 4.1 | 3.260000e+01 | 36.7 |
| 39 | 39 | Örnsköldsvik | False | False | 3.1 | 2.270000e+01 | 25.8 |
| 40 | 40 | Östersund | True | True | 0.9 | 1.115000e+02 | 0.0 |
edge_info = pd.DataFrame(autonomax.edge_info())
edge_info
| From | To | Type | Flow | Cost | Distance | |
|---|---|---|---|---|---|---|
| 0 | Skellefteå | Umeå | SUB | 19.5 | 731.139160 | 111 |
| 1 | Eskilstuna | Västerås | SUB | 26.3 | 244.508415 | 43 |
| 2 | Skövde | Örebro | SUB | 13.5 | 657.432752 | 132 |
| 3 | Lidköping | Örebro | SUB | 14.6 | 841.276358 | 148 |
| 4 | Stockholm | Västerås | SUB | 7.0 | 234.688115 | 101 |
| 5 | Linköping | Norrköping | SUB | 11.5 | 116.139455 | 44 |
| 6 | Motala | Örebro | SUB | 3.6 | 110.457934 | 92 |
| 7 | Boden | Kiruna | SUB | -4.0 | 637.913000 | 291 |
| 8 | Sandviken | Östersund | CORE | 0.0 | 3130.000000 | 313 |
| 9 | Linköping | Vetlanda | SUB | -7.4 | 389.358963 | 138 |
| 10 | Sundsvall | Östersund | CORE | 111.5 | 1660.000000 | 166 |
| 11 | Kalmar | Västervik | SUB | 5.6 | 300.208566 | 139 |
| 12 | Halmstad | Helsingborg | SUB | -6.1 | 145.447337 | 79 |
| 13 | Umeå | Örnsköldsvik | SUB | 22.7 | 849.479945 | 111 |
| 14 | Karlstad | Örebro | SUB | 0.9 | 29.229970 | 77 |
| 15 | Halmstad | Varberg | SUB | 9.5 | 167.432227 | 65 |
| 16 | Lidköping | Vänersborg | SUB | -13.4 | 206.938975 | 60 |
| 17 | Uddevalla | Vänersborg | SUB | 9.8 | 39.823253 | 21 |
| 18 | Gävle | Sandviken | SUB | 2.9 | 21.463257 | 25 |
| 19 | Hudiksvall | Sundsvall | SUB | 3.9 | 99.906716 | 81 |
| 20 | Sandviken | Västerås | CORE | 9.7 | 1100.000000 | 110 |
| 21 | Sundsvall | Örnsköldsvik | SUB | -25.8 | 1177.683887 | 127 |
| 22 | Jönköping | Motala | SUB | 1.2 | 52.590906 | 108 |
| 23 | Sundsvall | Västerås | CORE | -81.1 | 3080.000000 | 308 |
| 24 | Eskilstuna | Nyköping | SUB | -4.6 | 119.995513 | 83 |
| 25 | Vetlanda | Växjö | SUB | -5.3 | 112.394025 | 72 |
| 26 | Borås | Varberg | SUB | -10.3 | 260.758783 | 84 |
| 27 | Haparanda | Luleå | SUB | 4.6 | 210.858567 | 124 |
| 28 | Luleå | Skellefteå | SUB | 15.1 | 742.410242 | 133 |
| 29 | Kristianstad | Växjö | SUB | 3.0 | 134.707658 | 120 |
| 30 | Norrköping | Västervik | SUB | -7.4 | 287.369532 | 112 |
| 31 | Falun | Sandviken | SUB | 2.3 | 48.115171 | 65 |
| 32 | Gävle | Uppsala | SUB | -1.9 | 37.924183 | 60 |
| 33 | Kalmar | Karlskrona | SUB | -1.6 | 45.527170 | 79 |
| 34 | Helsingborg | Malmö | SUB | -3.9 | 67.318060 | 60 |
| 35 | Göteborg | Uddevalla | SUB | 5.8 | 117.417503 | 70 |
| 36 | Malmö | Trelleborg | SUB | -1.3 | 18.150077 | 34 |
| 37 | Västerås | Örebro | SUB | -36.7 | 1050.855609 | 93 |
| 38 | Boden | Luleå | SUB | 8.5 | 58.656839 | 32 |
| 39 | Eskilstuna | Norrköping | SUB | -20.6 | 681.069465 | 102 |
| 40 | Borås | Skövde | SUB | 11.0 | 384.262775 | 105 |
core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost
print(f'core = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6
core = 8970.000 subnet = 11430.910 ------------------ total = 20400.910
visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))